// https://www.lintcode.com/problem/permutations-ii/

public class Solution {
    /*
     * @param :  A list of integers
     * @return: A list of unique permutations
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        // write your code here
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        if (nums.length > 0) {
            _permuteUnique(nums, 0, ret);
        } else {
            ret.add(new ArrayList<>());
        }
        return ret;
    }
    
    protected void _permuteUnique(int[] nums, int start, List<List<Integer>> ret) {
        if (start == nums.length) {
            List<Integer> perm = new ArrayList<>();
            for (int i = 0; i < nums.length; ++i) {
                perm.add(nums[i]);
            }
            ret.add(perm);
        } else {
            for (int i = start; i < nums.length; ++i) {
                // 处理去重
                if ((i == start) || ((nums[i] != nums[i - 1]) && (nums[i] != nums[start]))) {
                    swap(nums, start, i);
                    _permuteUnique(nums, start + 1, ret);
                    swap(nums, start, i);
                }
            }
        }
    }
    
    protected void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
};